/*
1.顺序表
实现动态顺序表：构建一个动态顺序表，初始化时指定容量（默认 4）。
在添加元素时，若空间不足则将容量翻倍；
删除元素后，若元素个数低于容量的四分之一且容量大于默认值，将容量减半。
需实现添加、删除、获取指定位置元素、获取顺序表长度等功能。

有序顺序表合并：给定两个有序顺序表，
编写函数将它们合并成一个新的有序顺序表，要求空间复杂度为 O (1)。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INIT_SIZE 4
#define  DATA_TYPE int
typedef struct list
{
    DATA_TYPE *data;
    int max_len;
    int len;
    
}list,*p_list;
//初始化
p_list Create_sqlist();
//获取指定位置元素
DATA_TYPE get_value_sqlist(p_list L , int pos);
//打印
void print_sqlist(p_list L);
//获取顺序表长度
int get_long_sqlist(p_list L);
//获取顺序表最大长度
int get_maxlong_sqlist(p_list L);
//增
int add_sqlist(p_list L , DATA_TYPE value, int pos );
//删除
int del_sqlist(p_list L , int pos);
//合并
p_list merge_sqlist(p_list L1 , p_list L2);

int main(int argc, char const *argv[])
{
    p_list s = Create_sqlist();
    p_list s1 = Create_sqlist();

    printf("s添加元素:\n");
    add_sqlist(s,1,1);
    add_sqlist(s,2,2);
    add_sqlist(s,3,3);
    add_sqlist(s,4,4);

    print_sqlist(s);
    printf("s顺序表长度为:%d\n",get_long_sqlist(s));
    printf("s顺序表最大长度为:%d\n",get_maxlong_sqlist(s));

    printf("\ns添加元素:\n");
    add_sqlist(s,5,5);

    print_sqlist(s);
    printf("s顺序表长度为:%d\n",get_long_sqlist(s));
    printf("s顺序表最大长度为:%d\n",get_maxlong_sqlist(s));

    printf("\ns删除元素(第3个):\n");
    del_sqlist(s,3);
    print_sqlist(s);
    printf("s顺序表长度为:%d\n",get_long_sqlist(s));
    printf("s顺序表最大长度为:%d\n",get_maxlong_sqlist(s));

    printf("获取指定位置元素(位置3):%d\n",get_value_sqlist(s,3));

    printf("\ns1添加元素:\n");
    add_sqlist(s1,6,1);
    add_sqlist(s1,8,2);
    add_sqlist(s1,9,3);
    add_sqlist(s1,10,4);
    print_sqlist(s1);

    printf("合并s与s1\n");
    print_sqlist(merge_sqlist(s,s1));
    
    return 0;
}


//初始化
p_list Create_sqlist()
{
    p_list L = (p_list)malloc(sizeof(list));//首先为顺序表结构体分配内存
    if (L == NULL) {
        printf("malloc for list structure failed\n");
        return NULL;
    }

    L->data = (DATA_TYPE*)malloc(sizeof(DATA_TYPE)*INIT_SIZE);// 为数据数组分配内存
    if (L->data == NULL)
    {
        printf("malloc failed\n");
        free(L);  // 释放之前分配的结构体内存
        return NULL;
    }
    //初始化
    memset(L->data,0,sizeof(DATA_TYPE)*INIT_SIZE);
    L->max_len = INIT_SIZE;
    L->len = 0;
    return L;
}

//获取指定位置元素
DATA_TYPE get_value_sqlist(p_list L , int pos)
{
    if (L == NULL || L->data == NULL)
    {
        printf("list is null\n");
        return -1;
    }

    if (pos < 1 || pos > L->len+1)
    {
        printf("pos is erorr\n");
        return -1;
    }

    return L->data[pos - 1];

}

//增
int add_sqlist(p_list L , DATA_TYPE value, int pos )
{
    if (L == NULL || L->data == NULL)
    {
        printf("list is null\n");
        return -1;
    }

    if (pos < 1 || pos > L->len+1)
    {
        printf("pos is erorr\n");
        return -1;
    }
    //扩容检查
    if (L->len >= L->max_len) {

        L->max_len *= 2;

    }

    for (int i = L->len; i >= pos; i--) {
        L->data[i] = L->data[i-1];
    }

    // 5. 插入新元素
    L->data[pos-1] = value;
    L->len++;

    return 0;   
}
//打印
void print_sqlist(p_list L)
{
    if (L == NULL || L->data == NULL)
    {
        printf("list is null\n");
        return ;
    }
    for (size_t i = 0; i < L->len; i++)
    {
        printf("%d ",L->data[i]);
    }
    printf("\n");
    
}
//获取顺序表长度
int get_long_sqlist(p_list L)
{
    if (L == NULL || L->data == NULL)
    {
        printf("list is null\n");
        return -1;
    }
    return L->len;
}
//获取顺序表最大长度
int get_maxlong_sqlist(p_list L)
{
    if (L == NULL || L->data == NULL)
    {
        printf("list is null\n");
        return -1;
    }
    return L->max_len;
}

//删除
int del_sqlist(p_list L , int pos)
{
    if (L == NULL || L->data == NULL)
    {
        printf("list is null\n");
        return -1;
    }
    if (pos < 1 || pos > L->len+1)
    {
        printf("pos is erorr\n");
        return -1;
    }
    for (int i = pos; i < L->len; i++) {
        L->data[i-1] = L->data[i];
    }
    L->len--;

    //缩容检查
    if (L->len <= (L->max_len/2)) {

        L->max_len /= 2;
    }

}

//合并
p_list merge_sqlist(p_list L1 , p_list L2)
{
    if (L1 == NULL || L2 == NULL || L1->data == NULL || L2->data == NULL) {
        printf("list is null\n");
        return NULL;
    }

    // 检查L1是否有足够空间,不够就扩大
    while (L1->max_len >= L1->len + L2->len)
    {
        L1->max_len *=2;
    }
    // 合并指针初始化
    int i = L1->len - 1;    // L1的最后一个元素
    int j = L2->len - 1;    // L2的最后一个元素
    int k = L1->len + L2->len - 1;  // 合并后的最后一个位置

    // 从后向前合并
    while (i >= 0 && j >= 0) 
    {
        if (L1->data[i] > L2->data[j]) 
        {
            L1->data[k--] = L1->data[i--];
        } else 
        {
            L1->data[k--] = L2->data[j--];
        }

    }
    // 处理L2剩余元素（如果有）
    while (j >= 0) {
        L1->data[k--] = L2->data[j--];
    }

    // 更新L1的长度
    L1->len += L2->len;

    return L1;
    
}

